import java.util.Random;

class Skiplist2 {
    class SkipListNode {
        int val;
        int cnt;  // 当前val出现的次数
        SkipListNode[] levels;  // start from 0
        SkipListNode() {
            levels = new SkipListNode[MAX_LEVEL];
        }
    }

    private double p = 0.5;
    private int MAX_LEVEL = 16;
    private SkipListNode head;  // 头结点
    private int level;  // 
    private Random random;

    public Skiplist2() {
        // 保存此level有利于查询（以及其他操作）
        level = 0;  // 当前 skiplist的高度（所有数字 level数最大的）
        head = new SkipListNode();
        random = new Random();
    }
    // 返回target是否存在于跳表中
    public boolean search(int target) {
        SkipListNode curNode = head;
        for (int i = level-1; i >= 0; i--) {
            /**
             * 遍历层的链表，如果目标值大于当前元素值则从则要从当前节点的层级开始从i开始遍历（重要）
             * 如果目标值不大于当前元素则从下一层开始遍历，还是从链表的头遍历（已经遍历的节点不在遍历）
             */
            while (curNode.levels[i] != null && curNode.levels[i].val < target) {
                curNode = curNode.levels[i];
            }
        }
        //上面是找到比target小数字中最大的，则该值的下一个就是目标值
        curNode = curNode.levels[0];
        return (curNode != null && curNode.val == target);
    }

    // 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
    public boolean erase(int num) {
        SkipListNode curNode = head;
        // 记录每层能访问的最右节点
        SkipListNode[] levelTails = new SkipListNode[MAX_LEVEL];

        for (int i = level-1; i >= 0; i--) {
            while (curNode.levels[i] != null && curNode.levels[i].val < num) {
                curNode = curNode.levels[i];
            }
            levelTails[i] = curNode;
        }
        //只拿一个就行
        curNode = curNode.levels[0];
        if (curNode != null && curNode.val == num) {
            if (curNode.cnt > 1) {
                curNode.cnt--;
                return true;
            }
            // 存在，删除
            for (int i = 0; i < level; i++) {
                if (levelTails[i].levels[i] != curNode) {
                    break;
                }
                //重新构建链表这里的levels相当于next，意思就是讲levelTails的next指向levelTails.next.next;
                levelTails[i].levels[i] = curNode.levels[i];
            }
            //这里判断head下的数组中那一层是null，如果是在需要将level--
            while (level > 0 && head.levels[level-1] == null) {
                level--;
            }
            return true;
        }
        return false;
    }

    // 插入一个元素到跳表。
    public void add(int num) {
        SkipListNode curNode = head;
        // 记录每层能访问的最右节点
        SkipListNode[] levelTails = new SkipListNode[MAX_LEVEL];
        for (int i = level-1; i >= 0; i--) {
            while (curNode.levels[i] != null && curNode.levels[i].val < num) {
                curNode = curNode.levels[i];
            }
            levelTails[i] = curNode;
        }
        curNode = curNode.levels[0];
        if (curNode != null && curNode.val == num) {
            // 已存在，cnt 加1
            curNode.cnt++;
        } else {
            // 插入
            int newLevel = randomLevel();
            if (newLevel > level) {
                for (int i = level; i < newLevel; i++) {
                    levelTails[i] = head;
                }
                level = newLevel;
            }
            //如果不存在则需要重新构建节点（http://zhangtielei.com/assets/photos_redis/skiplist/skiplist_insertions.png）
            SkipListNode newNode = new SkipListNode();
            newNode.val = num;
            newNode.cnt = 1;
            for (int i = 0; i < level; i++) {
                //这里的意思就是讲节点插入到比他小的最大值与比他大的最小值的节点中间
                newNode.levels[i] = levelTails[i].levels[i];
                levelTails[i].levels[i] = newNode;
            }
        }
    }

    private int randomLevel() {
        int level = 1;  // 注意思考此处为什么是 1 ？
        while (random.nextDouble() < p && level < MAX_LEVEL) {
            level++;
        }
        return level > MAX_LEVEL ? MAX_LEVEL : level;
    }

    public static void main(String[] args) {
        Skiplist2 skiplist2 = new Skiplist2();
        for (int i = 1; i < 8; i++) {
            skiplist2.add(i);
        }

        System.out.println(skiplist2.head);
        System.out.println("1");
        boolean search = skiplist2.search(5);
        boolean search1 = skiplist2.erase(5);
        System.out.println(search);
        System.out.println(search1);
    }

    public int minArray(int[] numbers) {

        for (int i = 0,j=1; i < numbers.length && j < numbers.length; i++,j++) {

        }
        return 1;
    }
}